home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / pccts.zip / update10.ms < prev    next >
Text File  |  1992-12-08  |  33KB  |  906 lines
  1. .de 1s
  2. .nr PS 11
  3. .nr VS 13
  4. .br
  5. .LP
  6. ..
  7. .de 2s
  8. .nr PS 11
  9. .nr VS 16
  10. .br
  11. .LP
  12. ..
  13. .de cB
  14. .nr PS 9
  15. .nr VS 11
  16. .br
  17. .LP
  18. .KS
  19. .LD
  20. .ft CW
  21. ..
  22. .de cE
  23. .DE
  24. .nr PS 11
  25. .nr VS 16
  26. .br
  27. .KE
  28. .ft R
  29. ..
  30. .2s
  31. .ce
  32. \s+4The Purdue Compiler Construction Tool Set\s-4
  33.  
  34. .ce
  35. \s+2Version 1.06 Update\s-2
  36.  
  37. .ce
  38. \fIDecember 1, 1992\fP
  39.  
  40. .NH
  41. Enhancements
  42. .PP
  43. This section describes the update of PCCTS Version 1.00 to Version
  44. 1.06 (1.01-1.05 were internal releases).  The list of changes here is
  45. not complete since many \*Qlittle\*U fixes were made (actually, the
  46. predicated parsing feature is major).  Here, we concentrate on the
  47. enhancements to the system; file \f(CWBUGS100\fP contains a list of
  48. the bug fixes incorporated in the 1.06 release.  In addition, note
  49. that the manual has not been updated and will not be until the next
  50. major release (or until we get around to it).
  51. .NH 2
  52. Predicated Parsing \(em \fBALPHA Version\fP
  53. .PP
  54. Normally, parsing is a function of syntax alone.  Semantics
  55. (meaning/value of the input) are not taken into account when parsing
  56. decisions are made\(emcontext-free parsing.  Typically, languages, such
  57. as C++, have some rules which require the lexical analyzer to consult
  58. the symbol table to determine what token (e.g. classname verses
  59. enumerated name verses typedef name) is given to the parser.  However,
  60. lexical analyzers have no context information except the current token
  61. of lookahead and must be coerced via flags to yield the various token
  62. types.  Ad hoc approaches become increasingly difficult to implement
  63. as the number of ambiguities (due to lack of semantic information) in
  64. a grammar rises.
  65. .PP
  66. Context dictates the scope of variables in programming languages.
  67. Because only the parser has context information, it is reasonable to
  68. assume that the parser is the correct place to maintain and access the
  69. symbol table; there are other situtations in which it is useful to
  70. have context direct parsing.  Unfortunately, most parser generators do
  71. not allow grammar actions to influence the parse; i.e. parsing is a
  72. function of syntax alone.  Because PCCTS generates recursive-descent
  73. LL(k) parsers in C, allowing user-defined C actions to influence
  74. parsing is a straightforward and natural addition to the PCCTS
  75. description meta-language.  Although bottom-up parsing strategies can
  76. allow actions to direct parsing, bottom-up parser have much less
  77. semantic information; i.e. LR and LALR techniques allow only
  78. \fIS\fP-attributed grammars whereas LL allows \fIL\fP-attributed
  79. grammars (for example, LL always knows which set of rules it is
  80. currently trying to match whereas LALR does not, in general; see your
  81. favorite book on parsing theory).
  82. .PP
  83. In this section, we introduce a rudimentary version of predicates,
  84. with a full implementation to appear in future releases.  To support
  85. context-sensitive parsing PCCTS 1.06 allows a new action type called
  86. \fIpredicate\fP (\f(CW-pr\fP must be used), which is denoted:
  87. .cB
  88. <<predicate>>?
  89. .cE
  90. .LP
  91. or, optionally,
  92. .cB
  93. <<predicate>>?[fail_action]
  94. .cE
  95. .LP
  96. where the second notation \*Qpasses\*U an argument of an action to the
  97. predicate operator \*Q\(CW?\fP\*U, which is executed upon predicate
  98. failure.  A predicate is a C action that evaluates to either true
  99. (success) or false (failure) and can be used for both \fIsemantic
  100. validation\fP and for \fIdisambiguating\fP syntactic conflicts in the
  101. underlying grammar.
  102. .PP
  103. Validation predicates are used as simple tests and are functionally
  104. equivalent to the following normal action:
  105. .cB
  106. if ( !predicate ) {\fIerror message; exit rule\fP}
  107. .cE
  108. .LP
  109. or, when a fail action is present:
  110. .cB
  111. if ( !predicate ) {fail_action}
  112. .cE
  113. .LP
  114. For example,
  115. .cB
  116. a   :   A <<pred>>? B
  117.     ;
  118. .cE
  119. .LP
  120. Matches \f(CWA\fP, evaluates \f(CWpred\fP, and matches \f(CWB\fP if
  121. \f(CWpred\fP is true else an error is reported (i.e. \*Q\f(CWfailed
  122. predicate 'pred'\fP\*U) and rule \f(CWa\fP is exited before matching
  123. \f(CWB\fP.  To generate a more useful error message, the user may
  124. specify a fail action:
  125. .cB
  126. a   :   A <<pred>>?[fail] B
  127.     ;
  128. .cE
  129. .LP
  130. which executes \f(CWfail\fP when \f(CWpred\fP evaluates to false.
  131. .PP
  132. A predicate which validates a production can, at the same time, be
  133. used to disambiguate a syntactically ambiguous grammar structure.  To
  134. be a candidate, a predicate must appear on the extreme left edge of a
  135. production.  Disambiguating predicates are used in the alternative
  136. prediction expressions to enable or disable certain alternative
  137. productions of a block (rule or subrule).  Parsing in this new
  138. environment can be viewed in this way:
  139. .IP "\fIstep 1: Disable invalid productions\fR"
  140. An \fIinvalid\fP production is a production whose disambiguating
  141. predicate evaluates to false.
  142. .IP "\fIstep 2: Parse as normal block\fP"
  143. Once a list of \fIvalid\fP productions has been found, they are parsed
  144. as a normal rule or subrule.
  145. .LP
  146. Essentially, disambiguating predicates \*Qgate\*U alternative
  147. productions in and out depending on their \*Qapplicability\*U.
  148. Productions without predicates have an implied predicate of
  149. \f(CW<<TRUE>>?\fP; i.e. they are always valid.
  150. .PP
  151. A single predicate can be used as both a validation and a
  152. disambiguating predicate\(emANTLR determines which way to use them
  153. automatically.  The role taken by a predicate depends on its location
  154. in the grammar.  Predicates are all considered validation predicates
  155. as they must always evaluate to true for parsing of the enclosing
  156. production to continue.  However, when a grammatical ambiguity is
  157. discovered, ANTLR searches for \fIvisible\fP predicates to
  158. disambiguate the construct.  A visible predicate is one which can be
  159. evaluated in a production prediction expression without consuming a
  160. token or executing an action (except initialization actions); e.g. all
  161. disambiguating predicates appear on the left edge of some production.
  162. Fail actions are not used in prediction expressions because a failed
  163. predicate disables a production; it does not report a syntax error
  164. unless no other \fIviable\fP predicates are present; a viable
  165. production is one which is predicted by the lookahead.  The action of
  166. moving a predicate into a prediction expression is called
  167. \fIhoisting\fP; currently, at most one predicate can be hoisted per
  168. ambiguous production.  In general, predicates may only be a function
  169. of:
  170. .IP "User variables"
  171. This is dangerous as hoisting may evaluate the predicate in a scope
  172. where the variable(s) does not exist; e.g. using rule parameters can
  173. be a problem if a predicate that references them is hoisted outside of
  174. the rule.
  175. .IP "Attributes"
  176. Only attributes in the left context can be used; i.e. attributes of
  177. rules/tokens created before the predicate is evaluated.
  178. .IP "Lookahead"
  179. The next \fIk\fP tokens of lookahead can be tested via \f(CWLA(i)\fP,
  180. \f(CWLATEXT(i)\fP.
  181. .LP
  182. Also, \fBpredicates may not have side-effects\fP (user must undo
  183. anything that was changed if they do; in other words, they must
  184. \*Qbacktrack\*U).  See the Future Work section for information
  185. regarding the use of predicates and extremely large lookahead buffers.
  186. .PP
  187. Consider the following simple grammar:
  188. .cB
  189. a   :   <<pred1>>? A B
  190.     |   <<pred2>>? A C
  191.     ;
  192. .cE
  193. .LP
  194. This grammar is LL(2) (\f(CW-k\ 2\fP) and ANTLR would not report an
  195. ambiguity.  However, it is LL(1) ambiguous (\f(CW-k\ 1\fP) and
  196. \f(CWantlr\ t.g\fP would generate a warning message:
  197. .cB
  198. t.g, line 1: warning: alts 1 and 2 of rule ambiguous upon { A }
  199. .cE
  200. .LP
  201. Now, if we allow predicates to be used with \f(CWantlr\ -pr\ t.g\fP,
  202. then ANTLR finds that both predicates are visible and can be used to
  203. disambiguate the production; it is up to the user to ensure that the
  204. predicates do, in fact, disambiguate the predicate.  ANTLR would
  205. generate code similar to the following:
  206. .cB
  207. a()
  208. {
  209. ...
  210.     if ( pred1 && LA(1)==A ) {
  211.     }
  212.     else if ( pred2 && LA(1)==A ) {
  213.     }
  214.     else \fIerror\fP;
  215. ...
  216. }
  217. .cE
  218. .LP
  219. The following grammars are syntactically and semantically equivalent
  220. to the above grammar, but the predicates are not hoisted trivially:
  221. .cB
  222. a   :   ( <<pred1>>? A B )
  223.     |   <<pred2>>? A C
  224.     ;
  225. .cE
  226. .LP
  227. ANTLR looks inside the subrule of production one and finds that
  228. \f(CWpred1\fP can be evaluated before executing an action and before
  229. matching a token; it is hoisted for use in the prediction expression
  230. of rule \f(CWa\fP.  Predicates can be hoisted from other rules as well:
  231. .cB
  232. a   :   b
  233.     |   c
  234.     ;
  235.  
  236. b   :   <<pred1>>? A B
  237.     ;
  238.  
  239. c   :   <<pred2>>? A C
  240.     ;
  241. .cE
  242. .LP
  243. Rule \f(CWa\fP would still have the same production prediction
  244. expression.  The following grammar does not have predicates that can be
  245. hoisted to disambiguate the prediction:
  246. .cB
  247. a   :   A <<pred1>>? B             /* cannot hoist past token */
  248.     |   <<action>> <<pred2>>? A C  /* cannot hoist past action */
  249.     ;
  250. .cE
  251. .PP
  252. Now, consider how a simplified version of K&R C variable and function
  253. declarations could be specified:
  254. .cB
  255. decl:   /* variable definition, function DECLARATION/DEFINITION */
  256.         type declarator ( func_body | ";" )
  257.     |   /* function DEFINITION */
  258.         declarator func_body
  259.     ;
  260.  
  261. type:   "int"
  262.     |   "float"
  263.     |   WORD
  264.     ;
  265.  
  266. declarator
  267.     :   WORD { "\e(" args "\e)" }
  268.     ;
  269.  
  270. func_body
  271.     :   ( decl )* "\e{" (decl)* (stat)* "\e}"
  272.     ;
  273. .cE
  274. .LP
  275. unfortunately, rule \f(CWdecl\fP is totally ambiguous in the LL(1)
  276. sense (and in the LL(k) sense) since \f(CWWORD\fP can begin both
  277. alternatives of rule \f(CWdecl\fP.  Increasing the lookahead to two
  278. tokens does not help as the alternatives are ambiguous upon \f(CWWORD\
  279. WORD\fP.  Alternative one could match \f(CWmy_type\ var\fP and
  280. alternative two could match \f(CWfunc\ my_type\fP; hence, the second
  281. alternative matches at least one invalid sentence.  This is because
  282. the \f(CW(\ decl\ )*\fP subrule of rule \f(CWfunc_body\fP, which would
  283. match the second \f(CWWORD\fP of \f(CWWORD\ WORD\fP, does not know if
  284. an argument list was seen previously or not.  The question of whether
  285. to match a parameter definition list after a declarator is
  286. context-sensitive because a function header may or may not have been
  287. seen immediately beforehand.
  288. .PP
  289. One way in which this subset could be recognized is to recognize a
  290. large superset of the language and then, using actions, verify that the
  291. input was valid:
  292. .cB
  293. decl:   {type} declarator ( func_body | ";" )
  294.     ;
  295. .cE
  296. .LP
  297. But, jamming everything together makes action introduction more
  298. complicated.  It is better to specify the input language exactly with
  299. predicates.
  300. .PP
  301. To overcome the ambiguity in rule \f(CWdecl\fP and to ensure that only
  302. a function declarator is followed by a parameter definition, we
  303. augment the grammar as follows:
  304. .cB
  305. decl:   <<int is_func;>>
  306.  
  307.         /* variable definition, function DECLARATION/DEFINITION */
  308.         type declarator > [is_func]
  309.         (   <<is_func>>?[printf("warning: declarator not func\en");]
  310.             func_body
  311.         |   ";"
  312.         )
  313.  
  314.     |   /* function DEFINITION */
  315.         declarator > [is_func]
  316.         <<is_func>>?[printf("warning: expecting func header not %s\en", LATEXT(1));]
  317.         func_body
  318.     ;
  319.  
  320. type:   "int"
  321.     |   "float"
  322.     |   <<LA(1)==WORD ? isTYPE(LATEXT(1)) : 1>>?
  323.         WORD
  324.     ;
  325.  
  326. declarator > [int is_func]
  327.     :   <<LA(1)==WORD ? !isTYPE(LATEXT(1)) : 1>>?
  328.         WORD ( "\e(" <<$is_func=1;>> args "\e)" | <<$is_func=0;>> )
  329.     ;
  330.  
  331. func_body
  332.     :   ( decl )* "\e{" (decl)* (stat)* "\e}"
  333.     ;
  334. .cE
  335. .LP
  336. In rule \f(CWtype\fP, we add a predicate that ensures that, if the
  337. lookahead is a \f(CWWORD\fP, that the \f(CWWORD\fP is, in fact, a
  338. user-defined type; nothing can be said if the lookahead is something
  339. else, so we return success in that case; i.e. the predicate does not
  340. apply for that lookahead (context).  If rule \f(CWdeclarator\fP is
  341. called, a failure of the predicate will report a semantic error.  In
  342. our example, the predicate is also hoisted for use as a disambiguating
  343. predicate in rule \f(CWdecl\fP.  The predicate in rule
  344. \f(CWdeclarator\fP ensures that, if the lookahead is a \f(CWWORD\fP,
  345. that the \f(CWWORD\fP is not a user-defined type.  As before, it is
  346. also hoisted to rule \f(CWdecl\fP to disambiguate the second
  347. production of that rule.  Both productions of rule \f(CWdecl\fP have
  348. predicates that are hoisted into the prediction expressions for those
  349. productions; ANTLR assumes that the hoisted predicates
  350. \fBcompletely\fP disambiguate the decision, which is true in our
  351. case.  The first predicate physically present in rule \f(CWdecl\fP
  352. ensures that, if a function body is coming up, the declarator was a
  353. function header.  The second predicate in rule \f(CWdecl\fP again
  354. ensures that a function header was seen before trying to match a
  355. function body.  The variable \f(CWis_func\fP is set to the return
  356. value of rule \f(CWdeclarator\fP, which is set by two simple actions in
  357. \f(CWdeclarator\fP.
  358. .PP
  359. Currently, the context under which predicates are evaluated may not be
  360. correct; i.e. currently ANTLR does not compute the context from which
  361. it hoists a predicate.  For example,
  362. .cB
  363. a   :   b B
  364.     |   (X Y | A C)
  365.     ;
  366.  
  367. b   :   <<pred>>? A
  368.     ;
  369. .cE
  370. .LP
  371. The predicate \f(CWpred\fP will be hoisted for use in disambiguating
  372. rule \f(CWa\fP.  However, the predicate will be evaluate regardless of
  373. whether \f(CWA\fP, which is its context, or \f(CWX\fP is on the input
  374. stream.  It may be invalid to apply the predicate when the lookahead
  375. is \f(CWX\fP.  The user may overcome this by changing \f(CWpred\fP
  376. thus:
  377. .cB
  378. a   :   b B
  379.     |   (X Y | A C)
  380.     ;
  381.  
  382. b   :   <<LA(1)==A ? pred : TRUE>>? A
  383.     ;
  384. .cE
  385. .LP
  386. which will ensure that the predicate is only evaluated when \f(CWA\fP
  387. is seen on the input stream.
  388. .PP
  389. Another problem area lies in that hoisting can occur in situations
  390. that will break the semantics.  For example:
  391. .cB
  392. a   :   b[3]
  393.     |   A
  394.     ;
  395.  
  396. b[int i]
  397.     : <<f($i)>>? A
  398.     ;
  399. .cE
  400. .LP
  401. The predicate \f(CWf(i)\fP will be hoisted to rule \f(CWa\fP where the
  402. parameter \f(CWi\fP is not even defined.  Either do not do this or put
  403. a predicate (dummy or otherwise) between the decision and the
  404. predicate you do not wish to be hoisted:
  405. .cB
  406. a   :   <<1>>? b[3]
  407.     |   A
  408.     ;
  409.  
  410. b[int i]
  411.     : <<f($i)>>? A
  412.     ;
  413. .cE
  414. .PP
  415. This is an alpha release feature in that it is not anywhere near what
  416. we want it to do and has NOT been thoroughly tested.  User beware.  We
  417. do not guarantee that the syntax of predicates will stay this way;
  418. however, the semantics will not change.  We want users to play with
  419. predicates to find new, better or different ways of doing things.  We
  420. \fBreally\fP want user feedback on these critters before a full
  421. implementation is developed.  For example, how do you want the parser
  422. to respond if no valid, viable production is found?
  423. .cB
  424. a   :   <<p1>>? A
  425.     |   <<p2>>? A
  426.     |   B
  427.     ;
  428. .cE
  429. .LP
  430. If the input were \f(CWC\fP, a correct error message would be reported:
  431. .cB
  432. line 1: syntax error at "C" missing { A B }
  433. .cE
  434. .LP
  435. This is the correct message because it is truly a syntax, as opposed
  436. to semantic, error.  On the other hand, upon input \f(CWA\fP, when
  437. predicates \f(CWp1\fP and \f(CWp2\fP are false, the parser reports the
  438. following bizarre message:
  439. .cB
  440. line 1: syntax error at "A"
  441. .cE
  442. .LP
  443. which is not very meaningful.  The fail function, \f(CWzzFAIL\fP,
  444. found that, in fact, \f(CWA\fP is syntactically valid and got confused
  445. because an error was raised; this is because the fail routine has no
  446. semantic information.  A suitable definition of error reporting in the
  447. predicate environment must be created.
  448. .PP
  449. Please send any suggestions/questions to \f(CWparrt@ecn.purdue.edu\fP,
  450. \f(CWhankd@ecn.purdue.edu\fP or use the email server mechanism at
  451. \f(CWpccts@ecn.purdue.edu\fP (send a \f(CWSubject:\fP line of
  452. \*Qquestion antlr\*U and fill in the body of the email with your
  453. suggestion/question).
  454. .NH 2
  455. 1.06 Is Written in 1.00
  456. .PP
  457. The grammar for the PCCTS meta-language (file format) has been
  458. implemented in Version 1.00, making heavy use of \f(CW#lexclass\fP
  459. directives.  File \f(CWlexhelp.c\fP has been eliminated due to the
  460. superiority of 1.00 to 1.00B.
  461. .NH 2
  462. ANTLR Compiles Under ANSI C
  463. .PP
  464. Because of the rewrite of the grammar and some rewrites of ANTLR code,
  465. ANTLR now compiles with ANSI compilers without a wimper (except for
  466. two \*Q\f(CWunknown escape sequence\fP\*U warnings).  Your mileage may
  467. vary.
  468. .NH 2
  469. Grammar Files Distributed
  470. .PP
  471. \f(CWantlr.g\fP and \f(CWdlg_p.g\fP are now included in the source
  472. distribution for 1.06.  Note that the 1.00 PCCTS (both ANTLR and DLG)
  473. are required to process these grammar files.  DO NOT DESTROY YOUR OLD
  474. COPY OF 1.00 PCCTS (at least save the executables).
  475. .NH 2
  476. Script Generates Makefiles for PCCTS Projects
  477. .PP
  478. A C program called \f(CWgenmk.c\fP is available in the \f(CWsupport\fP
  479. directory of the PCCTS release which has the following usage:
  480. .LP
  481. \f(CWgenmk project f1.g f2.g ... fn.g\fP
  482. .LP
  483. It generates a makefile that creates an executable, \f(CWproject\fP,
  484. from a set of grammar files.  For example, \f(CWgenmk\ t\ t.g\fP
  485. generates:
  486. .cB
  487. #
  488. # PCCTS makefile for: t.g
  489. #
  490. DLG_FILE = parser.dlg
  491. ERR_FILE = err.c
  492. HDR_FILE = stdpccts.h
  493. TOK_FILE = tokens.h
  494. K = 1
  495. ANTLR_H = .
  496. BIN = .
  497. ANTLR = $(BIN)/antlr
  498. DLG = $(BIN)/dlg
  499. CFLAGS = -I. -I$(ANTLR_H)
  500. AFLAGS = -fe err.c -fh stdpccts.h -fl parser.dlg -ft tokens.h -k $(K)
  501. -gk
  502. DFLAGS = -C2 -i
  503. GRM = t.g
  504. SRC = scan.c t.c err.c
  505. OBJ = scan.o t.o err.o
  506. .cE
  507. .cB
  508. t: $(OBJ) $(SRC)
  509.         cc -o t $(CFLAGS) $(OBJ)
  510.  
  511. t.c parser.dlg : t.g
  512.         $(ANTLR) $(AFLAGS) t.g
  513.  
  514. scan.c : parser.dlg
  515.         $(DLG) $(DFLAGS) parser.dlg scan.c
  516. .cE
  517. .LP
  518. This program is handy when beginning a new PCCTS project or when first
  519. learning about PCCTS.
  520. .NH 2
  521. DLG Supports Case Insensitive Scanners
  522. .PP
  523. DLG has two new options which provide control over the case
  524. sensitivity of the generated scanner.  Specifically, case
  525. insensitivity implies that when a character is referenced in a regular
  526. expression, DLG behaves as if the user had typed both upper and lower
  527. case versions of that character; i.e. \f(CW(\fIa\f(CW|\fIA\f(CW)\fR
  528. where \fIa\fP is some character.  The new options are:
  529. .IP \f(CW-ci\fP
  530. Make lexical analyzer case insensitive
  531. .IP \f(CW-cs\fP
  532. Make lexical analyzer case sensitive (default).
  533. .NH 2
  534. Delayed Lookahead Fetches in Generated Parser
  535. .PP
  536. Currently, PCCTS generates parsers which always have \fIk\fP tokens of
  537. lookahead.  This is done by following the strategy that another token
  538. is fetched (\f(CWzzCONSUME\fP) when one is matched (\f(CWzzmatch\fP).
  539. This can be a problem for actions that need to occur after a token has
  540. been matched, but before the next token of lookahead is fetched.  This
  541. is somewhat overcome in PCCTS 1.00 by delaying the fetch if an action
  542. is found immediately after a token reference.  With the new delayed
  543. lookahead scheme, the next token is not consumed until the next match
  544. is required.  This means that any action before the next match (not
  545. necessarily adjacent to the previous match) will be executed before a
  546. lookahead fetch occurs.  Turn on ANTLR option \f(CW-gk\fP and DLG
  547. option \f(CW-i\fP to enable this feature.  This feature appears to
  548. work with AST's and attributes with the constraints mentioned below in
  549. the incompatibilities section (e.g. use of \f(CWLA(\fIi\f(CW)\fR and
  550. \f(CWLATEXT(\fIi\f(CW)\fR has been restricted).  It has been tested
  551. with the C (\fIk>\fP1 and Pascal (\fIk==\fP1) examples provided in the
  552. release and with several other large grammars.
  553. .PP
  554. This feature is primarily useful for developers of interactive tools.
  555. Previously, it was \fBreally\fP hard to get PCCTS to generate truly
  556. interactive tools.  It appeared as if the parser was always waiting on
  557. a token fetch rather than executing an appropriate action.  E.g. in
  558. PCCTS 1.00,
  559. .cB
  560. a : ( "A" "B" "C" "\en" ) <<printf("got it\en");>>
  561.   ;
  562. .cE
  563. .LP
  564. would not print \f(CWgot\ it\fP until one token after the newline had
  565. been typed.  PCCTS 1.06 will generate parsers that print the message
  566. immediately upon newline and will exit without waiting for another
  567. token as there are no token references following the action.
  568. .PP
  569. Another way in which delayed lookahead is useful lies in translators
  570. which add symbols to the symbol table which must be examined by a
  571. lexical action.  If a lookahead fetch occurs too fast, the lexical
  572. action may miss the introduction of a symbol into the symbol table.
  573. .PP
  574. This feature is a bit flaky for the moment\(em\f(CWLA(\fIi\f(CW)\fR
  575. and \f(CWLATEXT(\fIi\f(CW)\fR will generally not have the same values
  576. as when the \f(CW-gk\fP option is not used (for \fIk\fP>=2).  Use
  577. attributes to access token values; the lookahead buffer is not really
  578. a user object.  If you insist upon accessing the lookahead buffer, use
  579. \f(CWLA(0)\fP and \f(CWLATEXT(0)\fP, which typically access the last
  580. token matched and last text matched respectively; this is
  581. distinguished from \f(CWLA(1)\fP, which means the next token of
  582. lookahead.  Accessing the next token of lookahead is invalid because
  583. it will not be fetched from the input stream until needed (just before
  584. the next decision or match).
  585. .NH 2
  586. Tutorials Available
  587. .PP
  588. With release 1.06, we are distributing both a beginning and advanced
  589. tutorial.  They have not been thoroughly \*Qdebugged\*U much are much
  590. better than nothing:
  591. .IP Beginning Tutorial
  592. This tutorial introduces the basic functionality of PCCTS by example.
  593. The user need not be familiar with parsing theory or other compiler tools,
  594. but any familiarity reduces the learning curve substantially.
  595. .IP Advanced Tutorial
  596. Constructing a translator can be viewed as an iterative refinement
  597. process moving from language recognition to intermediate-form
  598. transformation.  This tutorial presents one possible sequence of
  599. refinements.  It uses as many features of PCCTS as is reasonable
  600. without regards to optimality.  It develops a compiler for a simple
  601. string manipulation language called \fIsc\fP.  The resulting compiler
  602. generates code for a simple stack machine.
  603. .NH 2
  604. Error Messages for \fIk>\fR1
  605. .PP
  606. Previous versions of PCCTS did not handle error message correctly for
  607. \fIk>\fP1.  For example, with two tokens of lookahead and the
  608. following grammar:
  609. .cB
  610. a : "A" "B" "D"
  611.   | "A" "C" "E"
  612.   ;
  613. .cE
  614. .LP
  615. an incorrect input of \(CWA\ D\ D\fP would yield:
  616. .cB
  617. line 1: syntax error at "A" missing A
  618. .cE
  619. .LP
  620. which is wrong (and incredibly confusing).  The new error mechanism
  621. generates the following error message upon the same incorrect input:
  622. .cB
  623. line 1: syntax error at "A D"; "D" not in { B C }
  624. .cE
  625. .LP
  626. which is infinitely superior.  Unfortunately, situations may arise
  627. when even this method will give an invalid message.  This may occur
  628. when alternatives have lookahead sequences which are permutations of
  629. the same tokens.
  630. .PP
  631. The definition of the standard error reporting function,
  632. \f(CWzzsyn()\fP has been modified.  The parameter list is now:
  633. .cB
  634. void
  635. zzsyn(char *text,
  636.       int tok,
  637.       char *egroup,
  638.       unsigned *eset,
  639.       int etok,
  640.       int k,
  641.       char *bad_text);
  642. .cE
  643. .LP
  644. Users can ignore this as it is transparent to them; unless, of course,
  645. the standard error reporting must be modified.  In addition,
  646. \f(CWzzFAIL\fP is now a function rather than a macro.
  647. .NH 2
  648. Trace Facility has Exit Macro
  649. .PP
  650. Previously, only an entry trace macro was inserted in parsers when the
  651. \f(CW-gd\fP ANTLR option was used.  An exit macro has been defined
  652. which resulted in \f(CWzzTRACE\fP becoming \f(CWzzTRACEIN\fP.  Also, a
  653. default trace macro prints out \*Q\f(CWenter\ rule\ \fIrule\fR\*U if no
  654. default trace macros are defined.  To define your own, the macro
  655. definitions must appear in the \f(CW#header\fP action.  As before, the
  656. sole argument to the trace routines is a string representing the rule
  657. which has been entered or is about to be exited.
  658. .NH 2
  659. Resource Limitation
  660. .PP
  661. Occasionally, ANTLR is unable to analyze a grammar submitted by the
  662. user.  This rare situation can only occur when the grammar is large
  663. and the amount of lookahead is greater than one.  A nonlinear analysis
  664. algorithm is used by PCCTS to handle the general case of \fILL(k)\fP
  665. parsing.  The average complexity of analysis, however, is near linear
  666. due to some fancy footwork in the implementation which reduces the
  667. number of calls to the full \fILL(k)\fP algorithm.
  668. .PP
  669. To avoid the situation where ANTLR takes 23 hours of CPU time and then
  670. runs out of virtual memory, use the \f(CW-rl\ \fIn\fR resource limit
  671. option where \fIn\fP is the maximum number of tree nodes to be used by
  672. the analysis algorithm.  An error message will be displayed, if this
  673. limit is reached, which indicates which grammar construct was being
  674. analyzed when ANTLR hit a non-linearity.  Use this option if ANTLR
  675. seems to go off to lunch and your disk start swapping; try
  676. \fIn\fP=10000 to start.  Once the offending construct has been
  677. identified, try to remove the ambiguity that ANTLR was trying to
  678. overcome with large lookahead analysis.  Future versions of PCCTS may
  679. incorporate a known algorithm that does not exhibit this exponential
  680. behavior.
  681. .NH 2
  682. Rule Prefix Option
  683. .PP
  684. An ANTLR option has been added that prefixes all functions
  685. corresponding to rules with a prefix.  This can be used to provide
  686. symbol hiding in your project to isolate the parser.  It can also be
  687. used to allow rule names that correspond to C keywords such as
  688. \(CWif\fR and \f(CWtypedef\fP.
  689. .NH 2
  690. Standard PCCTS Header
  691. .PP
  692. Two new ANTLR options have been added that control the creation of a
  693. standard PCCTS header file \(em \f(CWstdpccts.h\fP.  Option
  694. \f(CW-gh\fP instructs ANTLR to create a file, \f(CWstdpccts.h\fP
  695. unless \f(CW-fh\fP is used, which contains all header information
  696. needed by non-PCCTS generated files that want to access PCCTS
  697. symbols.  For example, it indicates the \fIk\fP of the parser, whether
  698. trees are being constructed, whether lookahead is to be delayed, and
  699. indicates what the user specified in the \f(CW#header\fP action in the
  700. grammar file.  Previously, the user had to manually construct this
  701. information from the grammar file in order to place the information in
  702. a non-PCCTS C file.  The \f(CW-fh\fP option is merely used to rename
  703. \f(CWstdpccts.h\fR.
  704. .NH 2
  705. Doubly-Linked AST's
  706. .PP
  707. A new function is available in \f(CWast.c\fP which will doubly-link
  708. any tree that is passed in.  To use this option, the user must define
  709. zzAST_DOUBLE in the \f(CW#header\fR directive or on the command-line
  710. of the C compile.  This defines \f(CWleft\fP and \f(CWup\fP fields
  711. automatically in the AST node typedef.  ANTLR generated parsers,
  712. normally, only construct singly-linked trees.  The fields can be
  713. filled in via code similar to the following:
  714. .cB
  715. #header <<
  716. ...
  717. #define AST_FIELDS    \fIuser-fields\fP;
  718. >>
  719.  
  720. <<
  721. main()
  722. {
  723.     AST *root = NULL;
  724.  
  725.     ANTLR(start(&root), stdin);
  726.     zzdouble_link(root, NULL, NULL);
  727. }
  728. .cE
  729. .LP
  730. where the function is defined as:
  731. .cB
  732. zzdouble_link(AST *t, AST *left, AST *up);
  733. .cE
  734. .NH 2
  735. C++ Compatible Parsers
  736. .PP
  737. PCCTS parsers may now be compiled with C++ compilers; i.e. the output
  738. is more ANSI C-like than before.  It has been successfully compiled
  739. with GCC 2.2, but not with GCC 1.37.  We do not guarantee anything.
  740. To be safe, use the \f(CW-ga\fP option so that PCCTS generates
  741. ANSI-style prototypes for functions generated from rules.  As a simple
  742. example, consider:
  743. .cB
  744. #header <<
  745. #include "charbuf.h"
  746. /* stdio.h is included, by default, but doesn't seem to bother stream.h */
  747. #include <stream.h>
  748. #include <stdlib.h>
  749. >>
  750.  
  751. #token "[\e \et\en]" <<zzskip();>>
  752.  
  753. <<
  754. main()
  755. {
  756.         ANTLR(a(), stdin);
  757.         cout << "end of C++ test\en";
  758. }
  759. >>
  760.  
  761. a       :       "A" "B" << cout << $1.text << $2.text << "\en"; >>
  762.         ;    
  763. .cE
  764. .LP
  765. which does not do much:
  766. .cB
  767. % t
  768. A B
  769. AB
  770. end of C++ test
  771. % 
  772. .cE
  773. .LP
  774. but it does compile with G++ 2.2 except that a warning is generated
  775. concerning \f(CWstrncpy()\fP not being declared before use.  This is
  776. trivial to fix, of course \(em by modifying the \f(CWcharbuf.h\fP
  777. file.  We compiled this with:
  778. .cB
  779. antlr -k 2 -gk -ga t.g
  780. Antlr parser generator   Version 1.06   1989-1992
  781. dlg -C2 -i parser.dlg scan.c
  782. dlg  Version 1.06   1989-1992
  783. g++ -I. -I../1.06/h -g -c scan.c
  784. g++ -I. -I../1.06/h -g -c t.c
  785. t.c: In function `struct Attrib zzconstr_attr (int, char *)':
  786. t.c:19: warning: implicit declaration of function `strncpy'
  787. g++ -I. -I../1.06/h -g -c err.c
  788. g++ -o t -I. -I../1.06/h -g scan.o t.o err.o
  789. .cE
  790. .LP
  791. We anticipate a rewrite to be more C++ sometime in the future.
  792. .NH
  793. Acknowledgements
  794. .PP
  795. We acknowledge Dan Lawrence of MDBS for the new error reporting
  796. facility concerning greater than one token of lookahead; Dana Hoggatt,
  797. also of MDBS, suggested the rule prefix idea (\f(CW-gp\fP option) and
  798. beta tested 1.06.  We thank Ed Harfmann of MDBS for creating the
  799. \f(CWmakefile.os2\fP files and porting it to the PC.  We acknowledge
  800. the following beta testers for 1.06 (alphabetically):  Thomas Buehlman
  801. (buehlman@iwf.mabp.ethz.ch), Peter Dahl (dahl@everest.ee.umn.edu),
  802. Chris Song (dsong@ncsa.uiuc.edu), Ariel Tamches (tamches@cs.UMD.EDU).
  803. We reference Russell Quong (quong@ecn.purdue.edu) of Purdue EE for his
  804. work with us on defining and refining predicates.  Ariel Tamches
  805. (tamches@cs.UMD.EDU) deserves attention for hacking on the particulars
  806. of the alpha-release predicates.
  807. .NH
  808. Machine Compatibility
  809. .PP
  810. PCCTS Version 1.06 has been tested on the following platforms:
  811. .IP "Sun 3/60"
  812. .IP "Sun SPARC I, II"
  813. .IP "Encore Multimax running Umax 4.3"
  814. .IP "Sun sparcstation IPX"
  815. .IP "NeXTstation"
  816. .IP "Decstation 3100 running Ultrix 4.2"
  817. .IP "DEC 5000"
  818. .IP "Linux on 386PC"
  819. .IP "Microsoft C 6.0 on PC OS/2, DOS"
  820. .IP "CSET/2 C compiler on PC OS/2"
  821. .IP "IBM RS6000"
  822. .IP "MIPS r2000"
  823. .NH
  824. Incompatibilities
  825. .PP
  826. Due to the bug fixes in 1.06, \*Qnew\*U ambiguities may appear in your
  827. grammar.  These were always there\(emANTLR simply did not find them.
  828. The analysis is more correct.
  829. .PP
  830. Calls to \f(CWzzTRACE\fP are no longer generated by the \f(CW-gd\fP
  831. option.  Now, \f(CWzzTRACEIN\fP, \f(CWzzTRACEOUT\fP are called at the
  832. beginning and end of functions, respectively.
  833. .PP
  834. The way in which PCCTS translates actions has been changed; before
  835. they were parsed with a C function, now the \f(CW#lexclass\fP facility
  836. is being used.  Some differences in translation may be discovered;
  837. e.g. a character may need to be escaped with \f(CW\e\fP whereas before
  838. the simple character was sufficient.
  839. .PP
  840. The user should no longer set the next token of lookahead or the text
  841. of the next token in the lexical analyzer using \f(CWLA(1)\fP and
  842. \f(CWLATEXT(1)\fP.  This is incompatible with the \f(CW-gk\fP option;
  843. hence, \f(CWNLA\fP and \f(CWNLATEXT\fP should be used instead where
  844. the \f(CWN\fP means \*Qnext\*U.
  845. .PP
  846. The \f(CW-ga\fP does not generate anything different as the code
  847. generator now dumps both K&R and ANSI with \f(CW#ifdef\fP's around the
  848. ANSI code.
  849. .PP
  850. Previously, no prototype was given when \f(CW-ga\fP was off.  Now,
  851. prototypes are always generated (with the appropriated
  852. \f(CW#ifdef\fP's).  These prototypes can conflict with the outside
  853. environment if the rule names are things like \f(CWif\fP and
  854. \f(CWstat\fP (which is a system call).  Use the \f(CW-gp\ \fIprefix\fR
  855. option to prefix all functions corresponding to rules with a string
  856. of your choice.
  857. .NH
  858. Future Work:
  859. .PP
  860. Predicates are still under development.  We expect an enhanced version
  861. of PCCTS that computes context and hoists more aggressively.
  862. .PP
  863. Often a grammar construct cannot be left factored to remove an
  864. ambiguity.  This typically arises in the situation that the common
  865. prefix can be arbitrarily long.  Fortunately, input is typically
  866. finite and one could scan past these constructs given enough
  867. lookahead.  This is not the same thing as backtracking as the parser
  868. never backs up; it simply looks ahead really far to make a decision.
  869. This can easily be handled with a predicate of the form:
  870. .cB
  871. <<is_this_found_ahead(\fIcontext\fP)>>?
  872. .cE
  873. .LP
  874. which would look ahead in the lookahead buffer to see if the
  875. \fIcontext\fP occurred within some finite number of tokens.  This
  876. concept is very similar to LR-Regular (LRR) parsers for those familiar
  877. with parsing theory.  Note that this is a very fast, cheap way to get
  878. something resembling the power of backtracking.
  879. .PP
  880. Attribute names are expected to be enhanced.  For example, instead of
  881. $i, $\fItoken_name\fP could be used:
  882. .cB
  883. a : WORD TYPE <<printf("%s %s\en", $WORD, $TYPE);>>
  884.   ;
  885. .cE
  886. .PP
  887. We expect to have a graphical user interface to PCCTS sometime in the
  888. future which allows entry of grammars using syntax diagram notation.
  889. The interface is expected to run under X Windows.
  890. .PP
  891. We anticipate a version that supports object-oriented programming and
  892. generates C++ instead of ANSI C.  For the moment, PCCTS is compatible
  893. with C++, but future versions will support C++.
  894. .PP
  895. Future versions, both C and C++, will be able to refer to PCCTS
  896. symbols by \f(CWpccts.\fIsymbol\fR instead of \f(CWzz\fIsymbol\fR.
  897. E.g. \f(CWzzskip()\fP will become \f(CWpccts.skip()\fP.
  898. .PP
  899. DLG will soon use lookahead of its own to allow the recognition of
  900. more complicated expressions; specifically, those which have
  901. left substrings in common with other regular expressions.
  902. .PP
  903. We expect future versions of PCCTS to dump grammar analysis and parser
  904. construction statistics such as how many rules required 1 token of
  905. lookahead, how many ambiguities etc...
  906.